package com.gxc.recursion;

import java.util.*;

/**
 * CC直播的运营部门组织了很多运营活动，每人活动需要花费一定的时间参与，
 * 主播每参加完一个活动即可得到一定的奖励，参与活动可以从任意活动开始，
 * 但一旦开始，就需要将后续活动参加完毕(注意:最后一个活动必须参加)，
 * 活动之间存在一定的依赖关系(不存在环的情况),现在给出所有的活动时间与依赖关系，
 * 以及给出有限的时间，请帮助主播计算在有限的时间内，能获得的最大奖励，以及需要的最少时长。
 *
 * 如上图数据所示，给定有限时间为10天。可以获取得最大奖励为:11700，需要的时长为:9天。
 * 参加的活动为BDFH四个。
 * 输入描述:第一行输入数据N与D，表示有N项活动，D表示给予的时长。0<N<=1000，0<D<=10000。
 * 从第二行开始到N+1行，每行描述一个活动的信息，其中第一项表示当前活动需要花费的时间t，第二项表示可以获得的奖励a，
 * 之后有N项数据，表示当前活动与其他活动的依赖关系，1表示有依赖，0表示无依赖。每项数据用空格分开
 * 输出描述:
 * 输出两项数据A与T，用空格分割。A表示所获得的最大奖励，T表示所需要的时长输入
 * 8 10
 * 3 2000 0 1 1 0 0 0 0 0
 * 3 4000 0 0 0 1 1 0 0 0
 * 2 2500 0 0 0 1 0 0 0 0
 * 1 1600 0 0 0 0 1 1 1 0
 * 4 3800 0 0 0 0 0 0 0 1
 * 2 2600 0 0 0 0 0 0 0 1
 * 4 4000 0 0 0 0 0 0 0 1
 * 3 3500 0 0 0 0 0 0 0 0
 * 输出
 * 11700 9
 *
 * 解法：
 * 构造一个结构：
 * 最后一个活动必须参加，所以从后往前倒：当前节点已用的天数day和奖励money,
 * 不同路线到达同一节点时，如果花费天数相同day，则只保留奖励money更多的
 */
public class MaximumReward {

    public static void main(String[] args) {
        int[][] daymoney = {{3, 2000}, {3, 4000}, {2, 2500}, {1, 1600}, {4, 3800},
                {2, 2600}, {4, 4000}, {3, 3500}};
        int[][] rel = {{0, 1, 1, 0, 0, 0, 0, 0},
                {0, 0, 0, 1, 1, 0, 0, 0},
                {0, 0, 0, 1, 0, 0, 0, 0},
                {0, 0, 0, 0, 1, 1, 1, 0},
                {0, 0, 0, 0, 0, 0, 0, 1},
                {0, 0, 0, 0, 0, 0, 0, 1},
                {0, 0, 0, 0, 0, 0, 0, 1},
                {0, 0, 0, 0, 0, 0, 0, 0}};

        int[] res = getMax(10, daymoney, rel);
        System.out.println(Arrays.toString(res));
        int[] res1 = {2, 3};
        System.out.println(Arrays.toString(res1));
    }

    public static int[] getMax(int limitDay, int[][] daymoney , int[][] rel) {
        int[] res = new int[2];
        Info lastInfo = toInfo(daymoney, rel);
        count(lastInfo);

        HashSet<Info> sets = new HashSet<>();
        Stack<Info> stack = new Stack<>();
        stack.push(lastInfo);

        int day = 0;
        int money = 0;
        while (!stack.isEmpty()) {
            Info pop = stack.pop();
            if (sets.contains(pop)) {
                continue;
            }
            sets.add(lastInfo);

            Iterator<Map.Entry<Integer, Integer>> iterator = pop.map.entrySet().iterator();
            while (iterator.hasNext()) {
                Map.Entry<Integer, Integer> next = iterator.next();
                Integer key = next.getKey();
                if (key < limitDay && next.getValue() > money) {
                    day = key;
                    money = next.getValue();
                }
            }
            for (Info info : pop.prev) {
                stack.push(info);
            }

        }
        res[0] = money;
        res[1] = day;
        return res;
    }

    private static void count(Info lastInfo) {
        countDayAndMoney(lastInfo, 0, 0);
    }

    private static void countDayAndMoney(Info info, int day, int money) {
        int totalDay = info.day + day;
        int totalMoney = info.money + money;
        info.putTreeMap(totalDay, totalMoney);
        for (Info bean:info.prev) {
            countDayAndMoney(bean, totalDay, totalMoney);
        }
    }

    /**
     * 输入数据转对象,返回最后的节点
     * @param daymoney
     * @param rel
     * @return
     */
    private static Info toInfo(int[][] daymoney, int[][] rel) {
        HashMap<Integer, Info> map = new HashMap<>();
        for (int i = 0; i < daymoney.length; i++) {
            Info info = new Info(daymoney[i][0], daymoney[i][1]);
            map.put(i, info);
        }

        for (int i = 1; i < rel.length; i++) {
            for (int j = 0; j < i; j++) {
                if (rel[j][i] == 1) {
                    Info cur = map.get(i);
                    Info prev = map.get(j);
                    cur.prev.add(prev);
                }
            }
        }
        return map.get(rel.length-1);
    }

    public static class Info{

        public int day;
        public int money;

        public LinkedList<Info> prev;
        //从最后的节点回推到当前节点的总时间和总奖励
        public PriorityQueue<DayAndMoney> queue;
        public Map<Integer, Integer> map;

        public Info(int day, int money) {
            this.day = day;
            this.money = money;
            prev = new LinkedList<>();
            queue = new PriorityQueue<>(new DayAndMoneyComparator());
            map = new HashMap<>();
        }

        public void putTreeMap(int totalDay, int totalMoney) {
            //当天数相同时，保留奖励更大的
            queue.add(new DayAndMoney(totalDay, totalMoney));
            adjust();
        }

        /**
         * 调整现存的天数和奖励，当天数变大时，保留奖励也同时变大的
         */
        private void adjust() {
            if (!queue.isEmpty()) {
                int min = Integer.MIN_VALUE;
                while (!queue.isEmpty()) {
                    DayAndMoney poll = queue.poll();
                    if (poll.money > min) {
                        map.put(poll.day, poll.money);
                        min = poll.money;
                    }
                }
            }
        }
    }

    public static class DayAndMoney {
        public int day;
        public int money;

        public DayAndMoney(int day, int money) {
            this.day = day;
            this.money = money;
        }
    }

    public static class DayAndMoneyComparator implements Comparator<DayAndMoney> {

        @Override
        public int compare(DayAndMoney o1, DayAndMoney o2) {
            if (o1.day == o2.day) return o2.money - o1.money;
            return o1.day - o2.day;
        }
    }
}
